Routers are networking or communications devices for routing and forwarding data packets over a network. Routers typically exchange information using routing protocols to discover the topology of the network and to determine paths for routing packets through the network. The exchanged information is stored in a Routing Information Base (RIB), which stores all IP routing information, and is responsible for next-hop selection from multiple available routes received from different peers. The router processes information in the RIB to determine how to forward packets from the router, with this information stored in a Forwarding Information Base (FIB). The FIB typically contains a subset of the RIB information, i.e., the address prefixes and their select next hops, for fast lookup during data forwarding. In the core of the network, it is possible for the FIB to contain hundreds of thousands of entries (e.g., one for each route in the FIB). When a router uses a distributed architecture, the same FIB is typically stored on each line card.
The global routing table size has been increasing faster than ever in a super-linear trend, mostly due to the practice of multihoming and traffic engineering. This has caused serious concerns from both academia and industry. Once the FIB becomes so large that it can no longer fit in the fast memory of routers' line cards, ISPs have to upgrade their line cards, eventually making Internet services more expensive. While solutions have been proposed to solve the routing table scalability problem in the long run by changing the routing architecture, Internet service providers (ISPs) need practical solutions soon, and FIB aggregation may be the most practical solution.
FIB aggregation reduces FIB size by combining entries whose prefixes are numerically aggregatable and whose next hops are the same. It is a software solution that can be applied to a single router without upgrading the hardware, changing the control plane, or affecting packets' forwarding paths. Thus it can be deployed incrementally and selectively in a network at operators' discretion. One of the fundamental tradeoffs in FIB aggregation is between aggregated table size and computation overhead. Spending too much CPU cycles in aggregating the table will delay the downloading of the table into the line cards, which may lead to packet loss or incorrect forwarding.
One of the most challenging problems in FIB aggregation is to quickly apply updates to the already aggregated table and still maintain good compression ratio. When a router receives a routing update, it has very limited amount of time to process the update and install the new FIB. When the FIB is already aggregated, one routing table change may lead to updating multiple FIB entries, because it may change the aggregatability of those entries. In some cases, there can be thousands or even tens of thousands FIB entries to be updated, even if there is only a single routing table change.